Schönen Abend, Schönen Tag, Schönen Abend. Also gute Nachrichten, ich habe es noch

geschafft, hochzuladen. Also der eineher hat mich gefragt, ob ich die,

ich meine und die Tizen auch schnell hochladen kann und habe ich noch gemacht.

Also wer sich das jetzt parallel anschauen will, kann das gerne machen. So.

So, herzlich willkommen zu unserer fünften Folle-Song. Wir schreiten immer weiter

vor an und wir benden heute auch den ersten großen Themenblock. Der erste

große Themenblock, wie Sie wissen, hat sich beschäftigt mit der Fragestellung

primär der Analyse von Algorithmen und hier haben wir uns zwei Sachen angeschaut.

Einmal die Laufzeit. Die Laufzeit hingen natürlich immer von Berechnungsmodellen ab.

Da hatten wir uns auch verschiedene Modelle angeguckt, insbesondere dann am Ende

auch das Rammodell. Wir hätten unterschiedliche Notationen kennengelernt zur

Laufzeitanalyse, also insbesondere die Täter, die O- und die Omniger-Notation.

Die eine, wenn Sie sich daran erinnern, die hier im Wesentlichen war eine Beschreibung

um eine bestimmte Funktion nach oben und nach unten hinabzuschätzen. Also wir

hatten dann im Wesentlichen, wenn das hier die Funktion f war, dann war das hier im

Wesentlichen eine Schranke nach oben, z.g. bzw. C1. Gleichzeitig hatten wir eine

Schranke nach unten, das war dann C2 mal G, C1 und C2 waren konstanten und das

ganzes eine asymptotische Betrachtung, das heißt, ja das bildet sich ganz schön aus,

aber das heißt im Wesentlichen ab einem gewissen Punkt, N0 muss das gelten. Und die

andere Notation dienten im Wesentlichen dazu, die Laufzeit nach oben, mitziehungsweise nach

unten hinabzuschätzen. Wir haben uns mit dem wunderschönen Themen der

Rekorsionen beschäftigt, ganz wichtig, das werden wir in Zukunft auch noch öfter sehen,

Rekorsionen. Und insbesondere haben wir uns auch Rekorensgleichungen dann angeguckt

und das wunderschöne Mastertheorie.

Wir wollten insbesondere bei den Rekorsionen verstehen, wie können wir das den analysieren?

Wir haben dann im ersten Schritt versucht, diesen Ablauf des Programms abstrakt zu beschreiben

und im nächsten Schritt haben wir gesehen, ja wir haben unterschiedliche Möglichkeiten,

wir können das beispielsweise einsetzen und versuchen das abzuleiten. Wir können aber auch

in relativ vielen Fällen uns das Leben einfacher machen mit dem wunderschönen Master Theorem.

Und bevor ich ein Ausblick gebe, noch mal ganz kurz, wir sind jetzt im Wesentlichen hier.

Das heißt, heute ist der letzte Blog in einem Analyse-Blog und danach geht es in Richtung Sortieren weiter.

Bevor wir mit unserem neuen Thema anfangen, wollte ich gerne eine kurze Wiederholung machen,

weil das Beispiel am Ende, es hat es nicht so gut gelaufen, wir waren alle ein bisschen stress

zu fragen, Hause. Und deswegen wollte ich das gerne noch mal machen, einfach damit Sie sehen,

wie einfach andernbar dieses Master Theorem ist, wenn man sich denn ein bisschen mehr konzentriert

als wir das in der letzten Follysum taten. Also das ist zur Wiederholung das Theorem.

Wir haben also gegeben eine Rekorens in folgen nach Form. Wichtig ist im Wesentlichen,

dass Sie, wenn Sie ein Programm haben, versuchen diese Form abzuleiten oder aber wenn Sie so eine Form

gegeben haben, dann müssen Sie im Wesentlichen nur noch die Variablen einsetzen.

Da passiert wirklich keine Magie. A und B sind im Wesentlichen zwei Konstanten und hier hinten

haben wir eine beliebige Funktion er von N. Das Master Theorem sagt, dass wir drei unterschiedliche

Fälle haben, Fall 1, Fall 2 und Fall 3 und auf den ersten Blick sieht es vielleicht ein bisschen

verwirrend oder verängstigend aus, wenn man sieht, ok, was ist das eigentlich für eine komische

Bedingung. Aber an sich ist die Bedingung überhaupt nicht schlimm. Das heißt, was müssen Sie machen

und zu gucken, ob Sie in einem der drei Fälle sind. Im Wesentlichen betrachten Sie die Funktion

F von N und schauen, ob Sie diese Laufzeit von dieser Funktion gut abschätzen können. So,

schauen wir uns das mal hier in den ganz konkreten Beispiel an. Also im Wesentlichen müssen wir,

um das Theorem anzuwenden, diese Funktionen er von N bestimmen und das konkrete Beispiel,

was wir hier hatten, das war im Wesentlichen unser Enhalver. Ok, also Schritt 1 ist, Sie gucken,

welche Aussage kann ich eigentlich über diese Funktion treffen und das, was dann hier hinten,